class Solution {
public:
    int numDecodings(string s) {
        if (s.size()==0) return 0;
        vector<int> f(s.size()+1, 0);
        f[0]=1;
        for (int i=0;i<s.size();i++) {
            int digit=(int)s[i]-(int)'0';
            if (1<=digit && digit<=9) f[i+1]+=f[i];
            if (i>0 && 0<=digit && digit<=9) {
                digit=(int)s[i-1]-(int)'0';
                if (1<=digit && digit<=9) {
                    digit=digit*10+(int)s[i]-(int)'0';
                    if (10<=digit && digit<=26) f[i+1]+=f[i-1];
                }
            }
        }
        return f[s.size()];
    }
};
